import heapq
import math

from OpenGL.GL import *
from OpenGL.GLU import *
import numpy

from common import *
from common.manager import Manager  

class Terrain(object):
	"""
	This class represents one map's terrain.
	"""
	
	HEIGHT_STEP = 0.01
	MAX_HEIGHT = 255 * HEIGHT_STEP
	DEFAULT_HEIGHT = 127 * HEIGHT_STEP
	MIN_HEIGHT = 0 * HEIGHT_STEP
	
	def __init__(self, map, width=None, height=None):
		"""
		Constructor.
		"""
		
		self.vertices = []
		self.map = map
		
		# Creates blocks according to the width and height values.
		if (width is None) or (height is None):
			self.blocks = None
		else:
			self.blocks = []
			
			self.__create_vertices(width, height)
			self.__create_blocks(width, height)
			self.__set_neighbours()
			
	def load_vertices(self, vertices):
		self.vertices = vertices
		
		self.blocks = []
		self.__create_blocks(len(self.vertices) - 1, len(self.vertices[0]) - 1)
		self.__set_neighbours()
		
	def __get_width(self):
		if self.blocks is None: return 0
		return len(self.blocks)
	width = property(__get_width)
	
	def __get_height(self):
		if self.blocks is None: return 0
		return len(self.blocks[0])
	height = property(__get_height)
	
	def __create_vertices(self, width, height, from_x=0, from_y=0):
		to_x = from_x + width + 1
		to_y = from_y + height + 1
		
		for i in range(from_x, to_x):
			if i >= len(self.vertices): self.vertices.append([])
			for j in range(from_y, to_y):
				vert = Vertex(i, j, i * Block.SIZE, j * Block.SIZE, Terrain.DEFAULT_HEIGHT)
				self.vertices[i].append(vert)
	
	def __create_blocks(self, width, height, from_x=0, from_y=0):
		to_x = from_x + width
		to_y = from_y + height
		
		for i in range(from_x, to_x):
			if i >= len(self.blocks): self.blocks.append([])
			for j in range(from_y, to_y):
				newBlock = Block(i, j)
				newBlock.vertices[0] = self.vertices[i][j]
				newBlock.vertices[1] = self.vertices[i + 1][j]
				newBlock.vertices[2] = self.vertices[i + 1][j + 1]
				newBlock.vertices[3] = self.vertices[i][j + 1]
				newBlock.set_middle()
				newBlock.set_normal()
				self.blocks[i].append(newBlock)
				
				
	
	def __set_neighbours(self, from_x=0, from_y=0, to_x=None, to_y=None):
		"""
		Sets all blocks neighbours.
		"""
		
		if to_x is None: to_x = self.width
		if to_y is None: to_y = self.height
		
		for i in range(from_x, to_x):
			for j in range(from_y, to_y):
				if j > 0:
					self.blocks[i][j].neighbours[S] = self.blocks[i][j-1]
					self.blocks[i][j].weights[S] = 1
				if j < to_y - 1:
					self.blocks[i][j].neighbours[N] = self.blocks[i][j+1]
					self.blocks[i][j].weights[N] = 1
					
				if i > 0:
					self.blocks[i][j].neighbours[W] = self.blocks[i-1][j]
					self.blocks[i][j].weights[W] = 1
					if j > 0:
						self.blocks[i][j].neighbours[SW] = self.blocks[i-1][j-1]
						self.blocks[i][j].weights[SW] = math.sqrt(2)
					if j < to_y - 1:
						self.blocks[i][j].neighbours[NW] = self.blocks[i-1][j+1]
						self.blocks[i][j].weights[NW] = math.sqrt(2)
						
				if i < to_x - 1:
					self.blocks[i][j].neighbours[E] = self.blocks[i+1][j]
					self.blocks[i][j].weights[E] = 1
					if j > 0:
						self.blocks[i][j].neighbours[NE] = self.blocks[i+1][j-1]
						self.blocks[i][j].weights[NE] = math.sqrt(2)
					if j < to_y - 1:
						self.blocks[i][j].neighbours[SE] = self.blocks[i+1][j+1]
						self.blocks[i][j].weights[SE] = math.sqrt(2)
	
	def set_size(self, newWidth, newHeight):
		prevWidth = self.width
		prevHeight = self.height
		
		if newWidth < prevWidth:
			for i in range(newWidth, prevWidth):
				for j in range(prevHeight):
					if self.blocks[i][j].occupation is None: continue
					self.map.remove(self.blocks[i][j].occupation)
				
			for j in range(self.height):
				self.blocks[newWidth - 1][j].neighbours[NE] = None
				self.blocks[newWidth - 1][j].neighbours[E] = None
				self.blocks[newWidth - 1][j].neighbours[SE] = None
				
			del self.blocks[newWidth:]
			del self.vertices[newWidth+1:]
		else:
			self.__create_vertices(newWidth - prevWidth - 1,
								prevHeight, prevWidth + 1, 0)
			self.__create_blocks(newWidth - prevWidth,
								prevHeight, prevWidth, 0)
			self.__set_neighbours(prevWidth - 1, 0, newWidth, self.height)
		
		if newHeight < prevHeight:
			for i in range(self.width):
				for j in range(newHeight, prevHeight):
					if self.blocks[i][j].occupation is None: continue
					self.map.remove(self.blocks[i][j].occupation)
				
			for i in range(self.width):
				del self.blocks[i][newHeight:]
				del self.vertices[i][newHeight+1:]
				self.blocks[i][newHeight - 1].neighbours[NW] = None
				self.blocks[i][newHeight - 1].neighbours[N] = None
				self.blocks[i][newHeight - 1].neighbours[NE] = None
				
		else:
			self.__create_vertices(self.width, newHeight - prevHeight - 1,
								0, prevHeight + 1)
			self.__create_blocks(self.width, newHeight - prevHeight,
								0, prevHeight)
			self.__set_neighbours(0, prevHeight - 1, self.width, newHeight)
	
	def can_build(self, block, width, height):
		current_col = block
		for i in range(width):
			if current_col is None or not(current_col.occupation is None):
				return False
			current = current_col
			
			for j in range(height):
				if current is None or not(current.occupation is None):
					return False
				current = current.neighbours[S]
				
			current_col = current_col.neighbours[E]
		
		return True
	
	def can_fit(self, block, width, height):
		"""
		States if a building starting at the given block
		fits the map, given its dimensions. 
		"""
		
		current_col = block
		for i in range(width):
			if current_col is None: return False
			current = current_col
			
			for j in range(height):
				if current is None: return False
				current = current.neighbours[S]
				
			current_col = current_col.neighbours[E]
			
		return True
	
	def occupy(self, occupation):
		from_x, from_y = occupation.top_left_block.id
		width = occupation.size[X]
		height = occupation.size[Y]
		from_y += 1 - height
		
		for i in range(from_x, from_x + width):
			for j in range(from_y, from_y + height):
				self.blocks[i][j].occupation = occupation
				
	def desoccupy(self, occupation):
		from_x, from_y = occupation.top_left_block.id
		width = occupation.SIZE[X]
		height = occupation.SIZE[Y]
		from_y += 1 - height
		
		for i in range(from_x, from_x + width):
			for j in range(from_y, from_y + height):
				self.blocks[i][j].occupation = None
				
	def get_path(self, from_block, to_block):
		if to_block.occupation:
			to_block = self.nearest_disoccupied(to_block)
			if not(to_block): return False 
		
		aStarNodes = {}
		aStarNodes[from_block] = AStarNode(from_block, 0, self.distance(from_block, to_block))
		
		openset = [aStarNodes[from_block]]
		closedset = []
		
		while len(openset) > 0:
			current = heapq.heappop(openset)
			
			if current.block == to_block:
				path = []
				
				c = current
				while c:
					path.insert(0, c.block)
					c = c.parent 
				
				return path
			
			closedset.append(current.block)
			
			for neighbour in current.block.open_neighbours():
				if neighbour in closedset: continue
				
				good_tentative = False
				tentative_g = current.g + 1
				
				if not(aStarNodes.has_key(neighbour)):
					newNode = AStarNode(neighbour, current.block)
					aStarNodes[neighbour] = newNode
					#heapq.heappush(openset, newNode)
					openset.append(newNode)
					good_tentative = True
				elif tentative_g < aStarNodes[neighbour].g:
					good_tentative = True
					
				if good_tentative:
					aStarNodes[neighbour].parent = current
					aStarNodes[neighbour].g = tentative_g
					aStarNodes[neighbour].h = self.distance(neighbour, to_block)
					
			heapq.heapify(openset)
		
		return False
	
	def distance(self, a, b):
		"""
		Returns the distance between two blocks.
		The diagonal distance is considered equal to the side distances.
		"""
		
		diag_steps = min(abs(a.id[X] - b.id[X]), abs(a.id[Y] - b.id[Y]))
		dir_steps = abs(a.id[X] - b.id[X]) + abs(a.id[Y] - b.id[Y])
		
		return -0.58578643762690485 * diag_steps + dir_steps
	
	def nearest_disoccupied(self, block, max_depth=4):
		current_layer = [block]
		next_layer = []
		
		visited = [block]
		
		for i in range(max_depth):
			for b in current_layer:
				if not(b.occupation):
					return b
				
				for neighbour in b.neighbours:
					if neighbour in visited: continue
					next_layer.append(neighbour)
					visited.append(neighbour)
			
			current_layer = next_layer 
			next_layer = []
		
		return False
	
	def render(self, grid=False):
		"""
		Renders the terrain.
		"""
		iMin, iMax, jMin, jMax = Manager.camera.getViewingConeInterval(Block.SIZE)
		
		glEnable(GL_CULL_FACE);
		iMin = max(0, iMin)
		jMin = max(0, jMin)
		iMax = min(self.width, iMax)
		jMax = min(self.height, jMax)				
		
		for i in range(iMin, iMax):
			for j in range(jMin, jMax):
				self.blocks[i][j].render()
		
		if grid:
			self.render_grid()
		glDisable(GL_CULL_FACE);
				
	def render_grid(self):
		"""
		Renders the terrain wire.
		"""
		
		iMin, iMax, jMin, jMax = Manager.camera.getViewingConeInterval(Block.SIZE)
		
		iMin = max(0, iMin)
		jMin = max(0, jMin)
		iMax = min(self.width + 1, iMax)
		jMax = min(self.height + 1, jMax)
		
		glDisable(GL_LIGHTING)
		glColor(1, 1, 1)
		
		for i in range(iMin, iMax):
			glBegin(GL_LINE_STRIP)
			for j in range(jMin, jMax):
				vert = self.vertices[i][j]
				glVertex3f(vert[X], vert[Y], vert[Z] + 0.02)
			glEnd()
			
		for j in range(jMin, jMax):
			glBegin(GL_LINE_STRIP)
			for i in range(iMin, iMax):
				vert = self.vertices[i][j]
				glVertex3f(vert[X], vert[Y], vert[Z] + 0.02)
			glEnd()
			
		glEnable(GL_LIGHTING)

	def tryPick(self, camera, x, y, viewport=None):
		"""
		Handles the terrain picking, returning the block under 
		the current mouse position. Returns None if there is none.
		"""
		
		if self.width == 0 or self.height == 0:
			return None
		
		buffer = glSelectBuffer(self.width * self.height * 4)
		if viewport is None:
			viewport = glGetInteger(GL_VIEWPORT)
		
		glRenderMode(GL_SELECT)
		
		glMatrixMode(GL_MODELVIEW)
		glPushMatrix()
		glMatrixMode(GL_PROJECTION)
		glPushMatrix()
		glLoadIdentity()
		gluPickMatrix(x, y, 2, 2, viewport)
		camera.setLens(load_identity=False)
		camera.setView()
		
		glInitNames()
		glPushName(0)
		
		index = 0
		for i in range(self.width):
			for j in range(self.height):
				glLoadName(index)
				self.blocks[i][j].render()
				index += 1
				
		glMatrixMode(GL_PROJECTION)
		glPopMatrix()
		glMatrixMode(GL_MODELVIEW)
		glPopMatrix()
		
		glFlush()
		glPopName()
		
		hits = glRenderMode(GL_RENDER)
		
		nearestHit = None
		for hit in hits:
			near, far, names = hit
			if (nearestHit is None) or (near < nearestHit[0]):
				nearestHit = [near, names[0]]
				
		if not(nearestHit is None):
			index = nearestHit[1]
			return self.blocks[index / self.height][index % self.height]
				
		return None

class Vertex(object):
	"""
	This class represents a terrain vertex.
	Initializes normal vector pointing to Z positive.
	"""
	
	def __init__(self, id_x, id_y, x, y, z):
		self.id = (id_x, id_y)
		self.position = [x, y, z]
		
		from random import random
		self.normal = [random(), random(), random()]
		
	def __getitem__(self, index):
		return self.position[index]
	
	def __setitem__(self, index, value):
		if index == Z:
			value = min(value, Terrain.MAX_HEIGHT)
			value = max(value, Terrain.MIN_HEIGHT)
		self.position[index] = value

class Block(object):
	"""
	This class represents a terrain block.
	"""
	
	SIZE = 0.5
	
	def __init__(self, x, y):
		"""
		Constructor.
		"""
		
		self.color = 0.6
		
		self.id = (x, y)
		self.neighbours = 8 * [None]
		self.weights = 8 * [None]
		self.vertices = 4 * [None]
		self.middle = 3 * [None]
		
		self.occupation = None
		self.canWalk = True
		self.canBuild = True
		
	def set_middle(self):
		self.middle = numpy.zeros(3)
		
		for v in self.vertices:
			self.middle += v.position
		self.middle /= len(self.vertices)
		
	def set_normal(self):
		pList = [None,None,None,None]
		vectorList = [[None,None],[None,None],[None,None],[None,None]]
		normalList = [None,None,None,None]
		for i in range(4):
			pList[i] = numpy.array([self.vertices[i].position[0],self.vertices[i].position[1],self.vertices[i].position[2]])
		vectorList[0][0] = pList[3]-pList[0]
		vectorList[0][1] = pList[1]-pList[0]
		vectorList[1][0] = pList[0]-pList[1]
		vectorList[1][1] = pList[2]-pList[1]
		vectorList[2][0] = pList[1]-pList[2]
		vectorList[2][1] = pList[3]-pList[2]
		vectorList[3][0] = pList[2]-pList[3]
		vectorList[3][1] = pList[0]-pList[3]
		for i in range(4):
			normalList[i] = (-numpy.cross(vectorList[i][0],vectorList[i][1])).tolist()
		for i in range(4):
			self.vertices[i].normal = normalList[i]
				
		
		
	def open_neighbours(self):
		group = []
		for n in self.neighbours:
			if n and not(n.occupation): group.append(n)
			
		return group
		
	def move(self, dz):
		for vert in self.vertices:
			vert[Z] += dz * Terrain.HEIGHT_STEP
			
		for block in self.neighbours:
			if block is None: continue
			block.set_middle()
			if not(block.occupation is None):
				block.occupation.set_middle()
			block.set_normal()
		self.set_middle()
		
		
		
	def render(self):
		"""
		Renders the block.
		"""
		
		if self.occupation is None:
			glColor(0, 0, self.color)
		else:
			glColor(self.color, 0, 0)
		glBegin(GL_QUADS)
		for vertex in self.vertices:
			glVertex3f(*vertex[:3])
			glNormal(*vertex.normal[:3])
		glEnd()
		
	def render_hovered(self):
		"""
		Renders the hovered effect of the block.
		"""
		
		glDisable(GL_LIGHTING)
		glColor(1, 1, 1, 0.5)
		glBegin(GL_QUADS)
		for vertex in self.vertices:
			glVertex3f(vertex[X], vertex[Y], vertex[Z] + 0.01)
		glEnd()
		glEnable(GL_LIGHTING)
		
	def render_selected(self):
		"""
		Renders the selected effect of the block.
		"""
		
		glDisable(GL_LIGHTING)
		glColor(1, 1, 0, 0.7)
		glBegin(GL_QUADS)
		for vertex in self.vertices:
			glVertex3f(vertex[X], vertex[Y], vertex[Z] + 0.02)
		glEnd()
		glEnable(GL_LIGHTING)


class AStarNode(object):
	def __init__(self, block, distance=0, heuristic=0, parent=None):
		self.block = block
		self.g = distance
		self.h = heuristic
		self.parent = parent
		
	def __get_f(self):
		return self.g + self.h
	f = property(__get_f)
	
	def __cmp__(self, other):
		return cmp(self.f, other.f)